package com.dycong.common.leetcode;

import java.util.Stack;

/**
 * 作用描述:给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * <p>
 * <p>
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
 * <p>
 * 示例:
 * <p>
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author dycong
 * @date 2019/12/19 8:53
 */
public class Trap_42 {

    public static void main(String[] args) {
        Trap_42 trap_42 = new Trap_42();
        int[] ints = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 2};
        int[] ints1 = new int[0];
        int[] ints2 = new int[]{5, 4, 1, 2};
        long exe = 0;
        long t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap(ints) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap(ints1) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap(ints2) + "   " + exe + "ms");


        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap2(ints) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap2(ints1) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap2(ints2) + "   " + exe + "ms");


        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap3(ints) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap3(ints1) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap3(ints2) + "   " + exe + "ms");


        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap4(ints) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap4(ints1) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap4(ints2) + "   " + exe + "ms");


        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap5(ints) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap5(ints1) + "   " + exe + "ms");
        t = System.currentTimeMillis();
        exe = System.currentTimeMillis() - t;
        System.out.println(trap_42.trap5(ints2) + "   " + exe + "ms");

    }

    public int trap(int[] height) {
        if (height.length < 2) {
            return 0;
        }
        return trap(0, height.length - 1, height);
    }

    /**
     * self 效率很好!!!
     * 思路：双指针，分升趋势、降趋势逻辑以及递归
     *
     * @param left
     * @param right
     * @param height
     * @return
     */
    public int trap(int left, int right, int[] height) {
        int firstindex = left;
        int capacity = 0;

        for (int i = left; i <= right; i++) {
            if (height[firstindex] <= height[i]) {
                capacity += capacity(firstindex, i, height);
                firstindex = i;
            }
        }
        if (firstindex != right) {
            //找到 first_index 之后最大高度
            int rightAfterMaxHeight = 0;
            int rightAfterMaxHeightIndex = firstindex + 1;
            for (int i = firstindex + 1; i < height.length; i++) {
                if (height[i] >= rightAfterMaxHeight) {
                    rightAfterMaxHeight = height[i];
                    rightAfterMaxHeightIndex = i;
                }
            }
            capacity += capacity(firstindex, rightAfterMaxHeightIndex, height);

            if (rightAfterMaxHeightIndex != right) {
                //rightAfterMaxHeightIndex 处开始新的数组逻辑，递归调用
                capacity += trap(rightAfterMaxHeightIndex, right, height);
            }
        }
        return capacity;
    }

    /**
     * 计算洼地容量
     *
     * @param first_index
     * @param last_index
     * @param height
     * @return
     */
    private int capacity(int first_index, int last_index, int[] height) {
        int waterLevel = Math.min(height[first_index], height[last_index]);
        int capacity = 0;
        for (int i = first_index + 1; i < last_index; i++) {
            capacity += waterLevel - height[i];
        }
        return capacity;
    }


    /**
     * 方法 1：暴力
     * 直观想法
     * <p>
     * 直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
     * <p>
     * 算法
     * <p>
     * 初始化 ans=0ans=0
     * 从左向右扫描数组：
     * 初始化 \text{max\_left}=0max_left=0 和 \text{max\_right}=0max_right=0
     * 从当前元素向左扫描并更新：
     * \text{max\_left}=\max(\text{max\_left},\text{height}[j])max_left=max(max_left,height[j])
     * 从当前元素向右扫描并更新：
     * \text{max\_right}=\max(\text{max\_right},\text{height}[j])max_right=max(max_right,height[j])
     * 将\min(\text{max\_left},\text{max\_right}) - \text{height}[i]min(max_left,max_right)−height[i] 累加到 \text{ans}ans
     */
    public int trap2(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        int capacity = 0;
        int length = height.length;
        for (int i = 0; i < length; i++) {
            int maxLeft = 0, maxRight = 0;
            for (int j = i; j >= 0; j--) {
                maxLeft = Math.max(height[j], maxLeft);
            }
            for (int j = i; j < length; j++) {
                maxRight = Math.max(height[j], maxRight);
            }

            capacity += Math.min(maxLeft, maxRight) - height[i];
        }

        return capacity;
    }

    /**
     * 方法 2：动态编程
     * 直观想法
     * <p>
     * 在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此，可以通过动态编程解决。
     * 算法
     * <p>
     * 找到数组中从下标 i 到最左端最高的条形块高度 \text{left\_max}left_max。
     * 找到数组中从下标 i 到最右端最高的条形块高度 \text{right\_max}right_max。
     * 扫描数组 \text{height}height 并更新答案：
     * 累加 \min(\text{max\_left}[i],\text{max\_right}[i]) - \text{height}[i]min(max_left[i],max_right[i])−height[i] 到 ansans 上
     */

    public int trap3(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        int capacity = 0;
        int length = height.length;
        int[] maxLeft = new int[length];
        int[] maxRight = new int[length];

        maxLeft[0] = height[0];
        maxRight[length - 1] = height[length - 1];

        for (int j = 1; j < length; j++) {
            maxLeft[j] = Math.max(height[j], maxLeft[j - 1]);
        }
        for (int j = length - 2; j >= 0; j--) {
            maxRight[j] = Math.max(height[j], maxRight[j + 1]);
        }
        for (int i = 0; i < length; i++) {
            capacity += Math.min(maxLeft[i], maxRight[i]) - height[i];
        }

        return capacity;
    }

    /**
     * 方法 3：栈的应用
     * 直观想法
     * <p>
     * 我们可以不用像方法 2 那样存储最大高度，而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。
     * <p>
     * 我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 \text{ans}ans 。
     * <p>
     * 算法
     * <p>
     * 使用栈来存储条形块的索引下标。
     * 遍历数组：
     * 当栈非空且 \text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]
     * 意味着栈中元素可以被弹出。弹出栈顶元素 \text{top}top。
     * 计算当前元素和栈顶元素的距离，准备进行填充操作
     * \text{distance} = \text{current} - \text{st.top}() - 1distance=current−st.top()−1
     * 找出界定高度
     * \text{bounded\_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]
     * 往答案中累加积水量\text{ans} \mathrel{+}= \text{distance} \times \text{bounded\_height}ans+=distance×bounded_height
     * 将当前索引下标入栈
     * 将 \text{current}current 移动到下个位置
     *
     * @param height
     * @return
     */
    public int trap4(int[] height) {
        int ans = 0, current = 0;
        Stack<Integer> st = new Stack<>();
        while (current < height.length) {
            while (!st.empty() && height[current] > height[st.peek()]) {
                int top = st.peek();
                st.pop();
                if (st.empty()) {
                    break;
                }
                int distance = current - st.peek() - 1;
                int boundedHeight = Math.min(height[current], height[st.peek()]) - height[top];
                ans += distance * boundedHeight;
            }
            st.push(current++);
        }
        return ans;
    }

    /**
     * 方法 4：使用双指针
     * 直观想法
     * <p>
     * 和方法 2 相比，我们不从左和从右分开计算，我们想办法一次完成遍历。
     * 从动态编程方法的示意图中我们注意到，只要 \text{right\_max}[i]>\text{left\_max}[i]right_max[i]>left_max[i] （元素 0 到元素 6），积水高度将由 left_max 决定，类似地 \text{left\_max}[i]>\text{right\_max}[i]left_max[i]>right_max[i]（元素 8 到元素 11）。
     * 所以我们可以认为如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。
     * 我们必须在遍历时维护 \text{left\_max}left_max 和 \text{right\_max}right_max ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。
     * <p>
     * 算法
     * <p>
     * 初始化 \text{left}left 指针为 0 并且 \text{right}right 指针为 size-1
     * While \text{left}< \text{right}left<right, do:
     * If \text{height[left]}height[left] < \text{height[right]}height[right]
     * If \text{height[left]} \geq \text{left\_max}height[left]≥left_max, 更新 \text{left\_max}left_max
     * Else 累加 \text{left\_max}-\text{height[left]}left_max−height[left] 到 \text{ans}ans
     * \text{left}left = \text{left}left + 1.
     * Else
     * If \text{height[right]} \geq \text{right\_max}height[right]≥right_max, 更新 \text{right\_max}right_max
     * Else 累加 \text{right\_max}-\text{height[right]}right_max−height[right] 到 \text{ans}ans
     * \text{right}right = \text{right}right - 1.
     */
    public int trap5(int[] height) {
        int left = 0, right = height.length - 1;
        int aws = 0;
        int leftMax = 0, rightMax = 0;

        while (left < right) {
            //只要 \text{right\_max}[i]>\text{left\_max}[i]right_max[i]>left_max[i] （元素 0 到元素 6），积水高度将由 left_max 决定
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    aws += leftMax - height[left];
                }
                left++;
                //反之亦然
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    aws += rightMax - height[right];
                }
                right--;
            }
        }
        return aws;
    }

}
